Cryptographic algorithms are widely used for encryption and decryption of messages, authentication, digital signatures and identification. The AES (Advanced Encryption Standard) is a well known cipher. AES is an exemplary symmetric block cipher. Block ciphers operate on blocks of plaintext and ciphertext, usually of 64 or 128 bits but sometimes longer. Stream ciphers are the other main type of cipher and operate on streams of plain text and cipher text 1 bit or byte (sometimes one word) at a time. With a block cipher, a particular plain text block will always be encrypted to the same cipher text block using the same key. However, to the contrary with a stream cipher, the same plain text bit or byte will be encrypted to a different bit or byte each time it is encrypted. Hence in the ECB (electronic code book) mode for block ciphers, each plain text block is encrypted independently. In another mode, encryption is also a function of the previous blocks.
AES is approved as an encryption standard by the U.S. Government. Unlike its predecessor DES (Data Encryption Standard), it is a substitution permutation network (SPN). AES is fast to execute in both computer software and hardware implementation, relatively easy to implement, and requires little memory. AES has a fixed block size of 128 bits and a key size of 128, 192 or 256 bits. Due to the fixed block size of 128 bits, AES operates on a 4×4 array of bytes. It uses key expansion and like most block ciphers a set of encryption and decryption rounds (iterations). Each round involves the same processes. Use of multiple rounds enhances security. Block ciphers of this type use in each round a substitution box or s-box. This operation provides non-linearity in the cipher and significantly enhances security.
Note that these block ciphers are symmetric ciphers, meaning the same algorithm and key are used for encryption and decryption, except usually for minor differences in the key schedule. As is typical in most modern ciphers, security rests with the (secret) key rather than the algorithm. The s-boxes or substitution boxes accept an n bit input and provide an m bit output. The values of m and n vary with the cipher and the s-box itself. The input bits specify an entry in the s-box in a particular manner well known in the field.
Many encryption algorithms are primarily concerned with producing encrypted data that is resistant to decoding by an attacker who can interact with the encryption algorithm only as a “Black Box” (input-output) model, and cannot observe internal workings of the algorithm or memory contents, etc due to lack of system access. The Black Box model is appropriate for applications where trusted parties control the computing systems for both encoding and decoding ciphered materials.
However, many applications of encryption do not allow for the assumption that an attacker cannot access internal workings of the algorithm. For example, encrypted digital media often needs to be decrypted on computing systems that are completely controlled by an adversary (attacker). There are many degrees to which the Black Box model can be relaxed. An extreme relaxation is called the “White Box” model. In a White Box model, it is presumed that an attacker has total access to the system performing an encryption, including being able to observe directly a state of memory, program execution, modifying an execution, etc. In such a model, an encryption key can be observed in or extracted from memory, and so ways to conceal operations indicative of a secret key are important.
The publication “White-Box Cryptography in an AES implementation” Lecture Notes in Computer Science Vol. 2595, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography pp. 250-270 (2002) by Chow et al. discloses implementations of AES that obscure the operations performed during AES by using table lookups (also referred to as TLUs) to obscure the secret key within the table lookups, and obscure intermediate state information that would otherwise be available in arithmetic implementations of AES. In the computer field, a table lookup table is an operation using a data structure (the table) to replace a computation with an array indexing operation.
Chow et al. (for his White Box implementation where the key is known at the computer code compilation time) uses 160 separate tables to implement the 11 AddRoundKey operations and 10 SubByte Operations (10 rounds, with 16 tables per round, where each table is for 1 byte of the 16 byte long—128 bit—AES block). These 160 tables embed a particular AES key, such that output from lookups involving these tables embeds data that would normally result from the AddRoundKey and SubByte operations of the AES algorithm, except that this data includes input/output permutations that make it more difficult to determine what parts of these tables represent round key information derived from the AES key.
An extension of Chow et al. was published by Olivier Billet et al. “Cryptanalysis of a White Box AES Implementation” in SAC 2004, LNCS 3357 pp. 227-240, 2005. The details of the processed basic operations are necessary to mount this attack. This means the attacker has to distinguish the set of operations to extract the operations per rounds, the MixColumn operation, etc.
Hence there are two basic principles in the implementation of secure computer applications (software). The first is called “Black Box” because it implicitly supposes that the user does not have access to the computer code nor any cryptographic keys themselves. The computer code security is based on the tampering resistance over which the application is running, as this is typically the case with SmartCards. For the “White Box”, it is assumed the (hostile) user has partially or fully access to the implemented code algorithms; including the cryptographic keys themselves. It is assumed the user can also become an attacker and can try to modify or duplicate the code since he has full access to it in a binary (object code) form. The White Box implementations are widely used (in particular) in DRM (Digital Rights Management) applications to protect e.g. audio and video content.
Software implementation of cryptographic building blocks are insecure in the White Box threat model where the attacker controls the computer execution process. The attacker can easily extract the (secret) key from the memory by just observing the operations acting on the secret key. For instance, the attacker can learn the secret key of an AES cipher software implementation by passively monitoring the execution of the key schedule algorithm. Also, the attacker could be able to retrieve partial cryptographic result and use it in another context (using in a standalone code, or injecting it in another program, as an example).
The conventional implementation of a block cipher in the White Box model is carried out by creating a set of table lookups. Given a dedicated cipher key, the goal is to store in a table the results for all the possible input messages. This principle is applied for each basic operation of the block cipher. In the case of the AES cipher, these are the shiftRow, the add RoundKey, the subByte and the mixColumns operations.
Since all the possible inputs have to be considered, the inputs are split into sets of bytes. The result after each operation on each byte is stored. Moreover, for security reasons, the input and output of the tables are masked through various methods (including permutations). The size of the tables differs according to the choice of the input decomposition (byte, half byte, double-bytes . . . ) and to the choice of the masking process (a XOR, random permutation etc.) See Chow et al.
When a block cipher has been implemented using a White Box approach, the code of the execution process is not particularly long and mainly consists of the lookup table accesses and masks managements, plus some extras. The first goal for an attacker reverse engineering such code is to retrieve the code to obtain, after simplification, an equivalent understandable and executable source code. Various tools exist to harden the code against reverse engineering threats. But, this is often not enough security.